package com.cet.algorithm.动态规划.背包问题;

import java.util.Arrays;
import java.util.OptionalInt;

/**
 * @program: cet-practice
 * @description: 分割等和子集
 * @author: 陈恩涛
 * @create: 2023-10-17 10:50
 **/
public class LC416 {

    /**
     * 数组是否能够拆分为两个和相等的子集
     * @param nums 待拆分数组
     * @return 结果
     */
    public boolean canPartition(int[] nums) {

        int sum  = 0;

        OptionalInt optionalInt = Arrays.stream(nums).reduce(Integer::sum);

        if (optionalInt.isPresent()) {
            sum = optionalInt.getAsInt();
        }

        // 如果数组和不为偶数，则一定无法拆分为两个等和的集合
        if (sum % 2 != 0) {
            return false;
        }

        // 转化为背包问题，容量为数组和一半的背包，能容纳的最大价值是否正好是数组和一半
        int bagSize = sum / 2;
        int[] dp = new int[bagSize + 1];

        // dp[j] 表示容量为j的背包最大能背的价值
        // dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
        // dp[0] = 0

        // 先遍历物品后遍历背包容量
        // 背包容量从大到小进行遍历
        for (int i = 0; i < nums.length; i++) {
            for (int j = bagSize; j >= nums[i] ; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }

        return dp[bagSize] == bagSize;

    }

    public static void main(String[] args) {
        System.out.println(new LC416().canPartition(new int[]{1, 2, 3, 5}));
    }
}
